package com.likou.top100;

import java.util.HashSet;

/**
 *  给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
 */
public class Demo03_最长不重复子串 {
    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("bbbbbb"));
        System.out.println(lengthOfLongestSubstring2("bbbbbb"));
    }
    public static int lengthOfLongestSubstring2(String s) {
        // 记录字符上一次出现的位置
        int[] last = new int[128];
        for(int i = 0; i < 128; i++) {
            last[i] = -1;
        }
        int n = s.length();

        int res = 0;
        int start = 0; // 窗口开始位置
        for(int i = 0; i < n; i++) {
            int index = s.charAt(i);
            start = Math.max(start, last[index] + 1);
            res   = Math.max(res, i - start + 1);
            last[index] = i;
        }

        return res;
    }
    public static int lengthOfLongestSubstring(String s) {
        int maxLength = 0;
        String maxStr = "";
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j <s.length() ; j++) {
                String str = s.substring(i,j+1);
                if (str.length()>maxLength && !isRepeated(str)){
                    maxLength = str.length();
                    maxStr = str;
                }
            }
        }
        System.out.println(maxStr);
        return maxLength;
    }

    /**
     * 判断字符串是否包含重复字符
     * @param s  字符串
     * @return  true 重复   false 不重复
     */
    public static boolean isRepeated(String s){
        HashSet<Character> characters = new HashSet<>();
        for (int i = 0; i <s.length() ; i++) {
            if (!characters.contains(s.charAt(i))){
                characters.add(s.charAt(i));
            }else{
                return true;
            }
        }
        return false;
    }
}
